Talk:Busy beaver function
Archive 1 It seems that overall the term "busy beaver function" is more popular. Should we consider moving this page? -- ve 19:23, September 5, 2015 (UTC) Should we rename the article to "Busy beaver function"? Yes No Weird alternative for S(n) Define s(n,c) to be maximum shifts function for finite tape limited to c cells. If this finite-tape TM's head escapes cells, it halts. Is g(n) = s(n,n) uncomputable? And can s(n,c) from some c be uncomputable? Ikosarakt1 (talk ^ ) 05:18, September 19, 2015 (UTC) : There are only finitely many (exponentially many) possible tape configurations, so we know that the machine doesn't halt iff it repeats a configuration. We can check if this happens by simply keeping track of all configurations the machine reaches and looking for repetition. Hence we can decide whether these machines halt, which makes s(n,c) computable. Indeed, this function is upper bounded by number of possible configurations which, I believe, is \(2^c\cdot c\cdot n\) (each of c cells can take 2 values, there are c possible head positions and n possible states) : By the way, this is closely related to . LittlePeng9 (talk) 06:50, September 19, 2015 (UTC) ::I was too slow and had a conflicting edit saying basically the same. A few things to add: your machine (I'll call it a Deterministic Bounded Automaton) can be thought of as a Turing machine where the input tape has the symbols [], symbolizing the left and right ends of the tape. For a TM to be an DBA, the TM's rules must restrict it from escaping or overwriting the end markers. Also, the input must be wrapped in these markers and [ has to be immediately to the left of the TM starting position. ::LittlePeng9 gave an upper bound and a computability proof, but didn't comment on how easy it is to compute. The DBA halting problem is primitive recursive (since the simulation time is bounded), and so is \(s(n,c)\). -- ve 07:20, September 19, 2015 (UTC) Fun fact BB(n) mod TREE(n) isn't computable function, but TREE(n) mod BB(n) is. Ikosarakt1 (talk ^ ) 04:01, September 23, 2015 (UTC) Can you prove the first statement? For what I know, it is possible that for all n large enough BB(n) is divisible by TREE(n). LittlePeng9 (talk) 04:54, September 23, 2015 (UTC) Which proof theory should I use? Ikosarakt1 (talk ^ ) 12:11, September 23, 2015 (UTC) : I suppose you are asking which axiomatic system to use. I would say that ZFC will be fine. LittlePeng9 (talk) 13:22, September 23, 2015 (UTC) : Sorry, I can make proof only in ZFC+"BB(n) mod TREE(n) is uncomputable". So yes, it's just a fun hypothesis. Ikosarakt1 (talk ^ ) 03:49, September 24, 2015 (UTC) :: What if the theory you described is inconsistent? -- ve 13:04, September 24, 2015 (UTC) ::It would mean that BB(n) mod TREE(n) is computable. Ikosarakt1 (talk ^ ) 14:24, September 24, 2015 (UTC) :::I think vell's point is that in this case your proof would be unsound, so that you would prove something that's not true. :::(it's also possible that this theory is inconsistent because ZFC is, but that's beyond the point) LittlePeng9 (talk) 14:30, September 24, 2015 (UTC) Shocking thoughts I've heard about universal Turing machines which can simulate others. But that makes BB(n) even more crazy. Imagine, say, 100-state TM (A) which can simulate another, billion-state TM (B) which returns insane number of 1's (corresponding to its recursive level). Or even worse, TM (B) may simulate some TM © with even more states. In that case, I think even BB(100) is hopeless to be beaten by explicitly defined recursive function (not even saying about proving its value). 19:53, October 25, 2015 (UTC) :Universal turing machines (those that simulate others) don't work exactly like that. They never halt, and are built such that they eventually simulate all possible turing machines. If a turing machine could simulate a turing machine with a greater number of states (and an equal/greater amount of colors) than the function would clearly be ill defined. For example, we'd have BB(100) equal at least BB(10^6), which would be equal to at least BB(10^12), which would be equal to at least BB(10^25), which would be equal to... and so forth till literally infinity. Direct simulation of turing machines with smaller amount of states is possible though (and with 2 tapes it's not even very hard), and you can see an example of that on my blog post here. Maybe called Googology Noob (talk) 11:07, January 22, 2016 (UTC) ::Actually, a Turing machine (A) with \(n\) states can simulate a machine (B) with \(m>n\) states. But here is the catch: (A) must operate with a specific input, not just empty input. An example is this machine of mine, which in principle can simulate a binary Turing machine with arbitrary number of states (the machine itself isn't binary, but there are standard ways of turning it into a binary TM). This doesn't make BB ill-defined, because we need to encode whole machine (B) into a string which would be a prefix to the input. LittlePeng9 (talk) 12:40, January 22, 2016 (UTC) :::In theory, you can have turing machines that can simulate any other turing machine given the right input. The problem is, with the small ones, the input is infinitely wide, and even with larger ones, having the machine that would write the input for the universal machine would usually take at least as many states as the original turing machine does. Tomtom2357 (talk) 08:55, January 25, 2016 (UTC) ::::LittlePeng9: That sounds interesting, but your link directs to the binary palindrome checker. Maybe called Googology Noob (talk) 15:08, January 30, 2016 (UTC) New Bounds I believe I have shown some new bounds of the Busy Beaver function using an accelerated FGH (f_0(n)=n+1, f_a+1(n)=f_an+2(n+2), f_a(n)=f_an+2(n+1)) here, mainly that \(\Sigma\)(25)>f_w2(3) and that \(\Sigma\)(27)>~f_w^2(12) (though obviously more bounds can be made on that). Can I put those bounds here? Maybe called Googology Noob (talk) 07:16, January 9, 2016 (UTC) : Your bound isn't a bound for \(\Sigma(27)\), but rather \(\Sigma(27,6)\), which is a multi-color variant of BB function (the symbols used are _,1,w,W,i,|,l , did I miss anything by a chance?). Although this is some bound, I honestly don't think it's of enough relevance to put it on this page - we tend to put multi-color bounds only if they beat some "milestone" in FGH. LittlePeng9 (talk) 08:05, January 9, 2016 (UTC) :: It uses all of those symbols, but not every symbol is used by each state (Obviously such a bound for \(\Sigma(27,6)\) would not be much). Each state uses exactly 2 colors. Maybe called Googology Noob (talk) 12:39, January 9, 2016 (UTC) :::That doesn't matter - for \(\Sigma (m,n)\) you can use no more than \(n\) colors in total. Deedlit11 (talk) 23:20, January 9, 2016 (UTC) ::::Oh, OK. Somehow I didn't realize that. Maybe called Googology Noob (talk) 06:07, January 10, 2016 (UTC) Other numbers estimated using BB(n)? I think for computable numbers the Busy Beaver function would be a good way to possibly envision their size. I know that BB(18) is greater than Graham's Number, and I heard that Loader's Number is somewhere around BB(160), but what abuot the following? - Zootzootplex - TREE(3) - SGC(13) - Tetrathoth - Gongulus - The various Fish numbers (aside from 4 and 7) - Kungulus - Meameamealokkapoowa oompa Does anyone have any estimates? —Preceding unsigned comment added by 148.75.113.243 (talk • ) 10:12, September 6, 2016 (UTC) :There's no way it was proven that Loader's number is somewhere around BB(160). What they meant was probably that some number around 160 is the smallest number such that some people figured out a proof that it's larger than Loader's number. It can be proven from the Church Turing thesis that if for each positive integer n'', you will eventually state a lower bound for ''BB(n'') and only do it once, then for some ''t, BB(n'') is larger than the lower bound for it that you will state for all ''n > t''. The same goes for the frantic frog function ''S(n''). There probably exists a 6 state 2 color turing machine that can some people have the resources to prove doesn't halt after TREE(3) steps but hasn't been proven to eventually halt and it can probably be proven that there's no proof in some very high level proof system that it never halts. If it does eventually halt, then ''S(6) is a whole lot larger than it's current proven lower bound. Although we probably don't have the resources to think of a mathematical proof of it, it can probably be proven from the Church Turing thesis that that turing machine doesn't even halt after a number of steps equal to Loader's number. Blackbombchu (talk) 18:40, September 6, 2016 (UTC) :1. Zootzootplex—Preceding unsigned comment added by 148.75.113.243 (talk • ) 12:34, September 7, 2016‎ (UTC) :::About TREE(3) and SCG(13): The thousand part is talking about bounds that are actually feasible to prove, while "12 to 50" means what we guess where the actual value falls in. :::About kungulus: in one interpretation (which seems to be advocated by Bowers himself), kungulus' growth rate is aroung \(\Gamma_0\) (the Feferman–Schutte ordinal), which is smaller than the Bachmann-Howard ordinal. There is a bound for Bachmann-Howard ordinal using 81 states and 10 colors, which is around a few hundred states and 2 colors using the color reduction technique. I still won't comment on meameamealokkapoowa oompa though, since one definition puts it in an incredibly high growth rate that I can't understand it. -- ☁ I want more ⛅ 13:53, September 7, 2016 (UTC) Rayo's number How many states do we need to beat Rayo's number? Googol, Googolplex or Loader's number? -- 17:52, September 7, 2016 (UTC) :Since Rayo's number is bigger than Sigma(), there is no way to result it. AarexWikia04 - 19:55, September 7, 2016 (UTC) :Rayo's number: This needs extremely many states, something that is not really much smaller than Rayo's number. :Googol: 6 is enough, 5 is conjectured to be not enough. :Googolplex: 7 is enough and I would personally conjecture 6 to be enough as well. :Loader's number: It is not known, but probably 1,000 states is sufficient. :Wythagoras (talk) 14:27, September 9, 2016 (UTC) \(\Sigma\) might be faster than we suspect I call Turing machine ™ "semi-universal" if it can simulate some other TM (particularly with larger number of states) with some input. Now imagine if there is 10-state TM which simulates some 1000-state TM which computes some fast-growing recursive function with sufficiently large input. What if \(\Sigma(10)\) is already larger that anything what we defined so far using computable function? Moreover, there might be "chains" of simulations: that 1000-state TM might be itself a simulator, for, say, \(10^{100}\)-state TM! (o_O) 05:13, November 14, 2016 (UTC) :Indeed. Just because we could build TM of some power with a bunch of states, it doesn't mean we can claim it isnt beat by a much lower numbered BB champion. Chronolegends (talk) 05:25, November 14, 2016 (UTC) :Although this is possible, it is rather unlikely that this approach will lead us to a new lower bounds on BB numbers. The reason for why I think so is that, in order for this to be feasible, the additional input allowing the 10-state TM to simulate the 1000-state TM would have to be relatively short, which would mean that, whatever the 1000-state TM was to do, it was terribly wasteful at it, given that a machine with so many states fewer was able to do the same job. In practice, if this were done, one would probably that the 1000-state TM was a less efficient version of the 10-state TM, rather than that the 10-state TM is a more efficient version of 1000-state TM. So all in all, I just think "semi-universal" TMs are plain unfeasible. :As for the remark about \(\Sigma(10)\) - heck, we don't even know this about \(\Sigma(5)\)! As unlikely as it seems, it might be the case that one of the unresolved 5-state TMs produces output vastly larger than any known computable notation. LittlePeng9 (talk) 09:29, November 14, 2016 (UTC) By the way, there is an idea about how to improve our current bounds for \(\Sigma(n)\). One can pick some UTM, like this. Then waste some states to write input correspondent to some known powerful TM, like this. 07:58, November 14, 2016 (UTC) :First, let me point out that using Wolfram's (2,3) TM would be probably the worst idea to simulate another TM one can think of. There are a few reasons for that, among them the fact that this TM needs an infinite, nonrepeating input and the fact that it never halts. To be honest, I don't even know under what measure this machine is universal (and it seems community doesn't know either...). :There are some proper UTMs which could be actually used for this purpose there are small 2-symbol UTMs (there is one with 19 states, there is also one with 18 states, but it lacks a halting instruction too). However, these UTMs require input of considerable size, which would take a long time to produce (we'd have to waste a lot of states), causing us to spend more states than the original machine had (using Baiocchi's machine and the hydra machine you've linked we'd probably only get a lower bound for \(\Sigma(n)\) for \(n\) on the order of thousands if not tens of thousands. :On a positive side though, such UTMs can be used for less specific bounds, for example to prove that \(\Sigma(n)\) outgrows any computable function. There are easier ways to do this as well, but still :) LittlePeng9 (talk) 09:29, November 14, 2016 (UTC) ::Wait what, this must be fastest! AarexWikia04 - 12:33, November 14, 2016 (UTC)